package test.day01;

public class ReverseLink {
	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public Node reverseDG(Node head) {
		if (head == null || head.next == null) {
			return head;
		}
		Node tmp = head.next;
		Node newHead = reverseDG(head.next);
		tmp.next = head;
		head.next = null;
		return newHead;
	}


//	public static Node reverse(Node head) {
//		if (head == null || head.next == null) {
//			return head;
//		}
//		Node temp = head.next;
//		Node newHead = reverse(head.next);
//		System.out.println(newHead.value);
//		temp.next = head;
//		head.next = null;
//		return newHead;
//	}

	public static void main(String[] args) {
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;

		// Node newHead = reverse(node1);
		Node newHead = reverse1(node1);
		System.out.println(newHead.value);
	}

	public static Node reverse(Node head) {
		if (head == null || head.next == null) {
			return head;
		}
		Node tmp = head.next;
		Node newHead = reverse(head.next);
		tmp.next = head;
		head.next = null;
		return newHead;
	}

	public static Node reverse1(Node head) {
		Node pre = null;
		Node curr = head;
		while(curr != null) {
			Node tmp = curr.next;
			curr.next = pre;
			pre = curr;
			curr = tmp;
		}
		return pre;
	}
}
